//
// Created by ASUS on 2023/9/20.
//
/*
 *
给定一个正整数 n ，请你统计在 [0, n] 范围的非负整数中，有多少个整数的二进制表示中不存在 连续的 1 。

示例 1:
输入: n = 5
输出: 5
解释:
下面列出范围在 [0, 5] 的非负整数与其对应的二进制表示：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数 3 违反规则（有两个连续的 1 ），其他 5 个满足规则。

示例 2:
输入: n = 1
输出: 2

示例 3:
输入: n = 2
输出: 3

提示:1 <= n <= 109
 */
#include <bits/stdc++.h>
using namespace std;

int findIntegers(int n) {
	int m = __lg(n), dp[m + 1][2];
	memset(dp, -1, sizeof(dp));
	function<int(int, bool, bool)> f = [&](int i, bool pre1, bool is_limit) -> int {
		if (i < 0) return 1;
		if (!is_limit && dp[i][pre1] >= 0) return dp[i][pre1];
		int up = is_limit ? n >> i & 1 : 1;
		int res = f(i - 1, false, is_limit && up == 0); // 填 0
		if (!pre1 && up == 1) res += f(i - 1, true, is_limit); // 填 1
		if (!is_limit) dp[i][pre1] = res;
		return res;
	};
	return f(m, false, true); // i 从 m 往小枚举，方便位运算
}